// 217、存在重复元素

// 使用indexof函数 
var findDuplicate = function (nums) {
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        if (nums.indexOf(nums[i]) != i) return nums[i];
    }
};

// 使用 set
var findDuplicate = function (nums) {
    let set = new Set();
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        if (set.has(nums[i])) return nums[i];
        else set.push(nums[i]);
    }
};

// 使用map+次数统计
var findDuplicate = function (nums) {
    let map = new Map();
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        if (map.has(nums[i])) return nums[i];
        else map.set(nums[i], 1);
    }
};


// 387. 字符串中的第一个唯一字符
var firstUniqChar = function (s) {
    let map = new Map();
    for (let i = 0; i < s.length; i++) {
        if (map.has(s.charAt(i))) map.set(s.charAt(i), map.get(s.charAt(i)) + 1);
        else map.set(s.charAt(i), 1);
    }

    for (let i = 0; i < s.length; i++) {
        if (map.get(s.charAt(i)) == 1) return i;
    }
    return -1;
};

// 136.只出现一次的数字
var singleNumber = function (nums) {
    const length = nums.length;
    let map = new Map();
    for (let i = 0; i < length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1);
        } else {
            map.set(nums[i], 1);
        }
    }

    for (let [key, value] of map.entries()) {
        if (value == 1) return key;
    }
};

// 217. 存在重复元素
// 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
var containsDuplicate = function(nums) {
    //  const length = nums.length;
    // for (let i = 0; i < length; i++) {
    //     if (nums.indexOf(nums[i]) != i) return true;
    // }
    // return false;
    const length = nums.length;
    let map = new Map();
    for (let i = 0; i < length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1);
        } else {
            map.set(nums[i], 1);
        }
    }

    for (let [key, value] of map.entries()) {
        if (value >= 2) return true;
    }
    return false;
};

// 异或运算符(^) ，我们了解下，这个运算符的功能
// 任何数和自己做异或运算，结果为 0，即 a⊕a = 0。
// 任何数和 0 做异或运算，结果还是自己，即 a⊕0 = a。
// 异或运算中，满足交换律和结合律，也就是a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a)=b⊕0 = b。
var singleNumber1 = function (nums) {
    const length = nums.length;
    let init = nums[0];
    for (let i = 1; i < length; i++) {
        init ^= nums[i];
    }
    return init;
};

// 242. 有效的字母异位词
var isAnagram = function (s, t) {
    const length1 = s.length;
    const length2 = t.length;
    let map = new Map();
    if (length1 != length2) return false;
    for (let i = 0; i < length1; i++) {
        if (map.has(s.charAt(i))) {
            map.set(s.charAt(i), map.get(s.charAt(i)) + 1);
        } else {
            map.set(s.charAt(i), 1);
        }
        if (map.has(t.charAt(i))) {
            map.set(t.charAt(i), map.get(t.charAt(i)) - 1);
        } else {
            map.set(t.charAt(i), - 1);
        }

    }

    for (let val of map.values()) {
        if (val != 0) return false;
    }
    return true;
};

isAnagram("rat", "car");

// 49. 字母异位词分组
// 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
var groupAnagrams = function(strs) {
    let map = new Map();
    let length = strs.length;
    if(length === 0) return res;
    for(let str of strs){
        let array = Array.from(str);
        array.sort();
        let key = array.toString();
        let list = map.get(key) ? map.get(key) : new Array();
        list.push(str);
        map.set(key, list);
    }
    return Array.from(map.values());
};


// 数组中出现次数超过一半的数字
var majorityElement = function (nums) {
    const length = nums.length;
    let map = new Map();
    for (let i = 0; i < length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1);
        } else {
            map.set(nums[i], 1);
        }
    }

    for (let [key, value] of map.entries()) {
        if (value > (length / 2)) return key;
    }
};


// 双指针
var majorityElement1 = function (nums) {
    const length = nums.length;
    const count = length / 2;
    nums.sort(function (a, b) { return a - b })
    console.log(nums);
    for (let i = 0; i < length; i = index) {
        let index = i + 1;
        while (index < length && nums[index] == nums[i]) { ++index };
        if (index - i > count) return nums[i];
    }
};


